package codetop.microsoft.T437;

import util.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: 18362
 * @Create: 2022-08-15 18:15:36 星期一
 */
class Solution {
    private int sum = 0;
    private Map<Long, Integer> map = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L, 1);
        tranverse(root, targetSum, 0);
        return sum;
    }

    private void tranverse(TreeNode root, int targetSum, long sum) {
        if (root == null)
            return;
        sum += root.val;
        this.sum += map.getOrDefault(sum - targetSum, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        tranverse(root.left, targetSum, sum);
        tranverse(root.right, targetSum, sum);
        map.put(sum, map.get(sum) - 1);
    }
}